#include <iostream>
#include <limits.h>
#include <vector>
#include <unordered_map>
#include <queue>
#include "UnionFindSet.h"

using namespace std;

namespace Matrix
{
    // V是记录结点关键词, W是记录结点关系, 邻接矩阵边初始都是最大值. Direction标志有向无向.
    template <class V, class W, W MAX_W = INT_MAX, bool Direction = false>
    class Graph
    {
    public:
        Graph(const V *vertexs, int n)
            // 初始化顶点集合以及邻接矩阵.
            : _vertexs(vertexs, vertexs + n), _matrix(n, vector<int>(n, MAX_W))
        {
            // 建立顶点映射.s
            for (int i = 0; i < n; i++)
            {
                _vIndexMap[vertexs[i]] = i;
            }
        }

        int getVertexIndex(const V &v)
        {
            auto iter = _vIndexMap.find(v);
            if (iter != _vIndexMap.end())
            {
                return iter->second;
            }
            else
            {
                throw invalid_argument("不存在的结点");
                return -1;
            }
        }

        // src和dest进行连接.
        void addEdge(const V &src, const V &dest, const W &weight)
        {
            // 先获取两个顶点的下标.
            int srci = getVertexIndex(src);
            int desti = getVertexIndex(dest);

            if (Direction == false)
            {
                _matrix[desti][srci] = weight;
            }
        }

        void print()
        {
            // 记录结点数:
            int n = _vertexs.size();

            // 先打印结点关键词对应映射关系:
            for (int i = 0; i < n; i++)
            {
                cout << "[" << i "]->" << _vertexs[i] << endl;
            }
            cout << endl;

            cout << " ";
            for (int i = 0; i < n; i++)
            {
                printf("%4d", i);
            }
            cout << endl;

            for (int i = 0; i < n; i++)
            {
                cout << i << " ";
                for (int j = 0; j < n; j++)
                {
                    // 如果没有顶点相连接.打印*
                    if (_matrix[i][j] == MAX_W)
                    {
                        printf("%4c", '*');
                    }
                    else
                    {
                        // 打印顶点之间的权重.
                        printf("%4d", _matrix[i][j]);
                    }
                }
                cout << endl;
            }
            cout << endl;
        }

        void bfs(const V& src)
        {
            //先找到对应的下标;
            int srci = getVertexIndex(src);
            queue<int> q;
            //原来标记是否遍历过的顶点.
            vector<bool> visited(_vertexs.size(), false);

            q.push(srci);
            visited[srci] = true;


            while(!q.empty())
            {
                int front = q.front();
                q.pop();
                cout << _vertexs[front] << " ";
                for(int i = 0; i < _vertexs.size(); i++)
                {
                    //判断相连并且没有遍历过.
                    if(_matrix[front][i] != MAX_W && visited[i] == false)
                    {
                        q.push(i);
                        visited[i] = true;
                    }
                }
                cout << endl;
            }
        }

        void _dfs(int srci, vector<bool>& visited)
        {
            cout << _vertexs[srci] << " ";
            visited[srci] = true;
            for(int i = 0; i < _vertexs.size(); i++)
            {
                if(_matrix[srci][i] != MAX_W && visited[i]== false)
                {
                    _dfs(i, visited);
                }
            }
        }


        void dfs(const V& src)
        {
            int srci = getVertexIndex(src);
            vector<bool> visited(_vertexs.size(), false);

            _dfs(srci, visited);
            cout << endl;
        }

        struct Edge
        {
            int _srci;
            int _desti;
            W _weight;
            Edge(int srci, int desti, const W& weight)
                :_srci(srci)
                ,_desti(desti)
                ,_weight(weight)
            {}

            bool operator>(const Edge& edge) const
            {
                return _weight > edge._weight;
            }
        };


        //强制生成默认构造;
        Graph() = default;

        //最小生成树, 最后返回权重.
        W Kruskal(Graph<V, W, MAX_W, Direction>& minTree)
        {
            int n = _vertexs.size();

            //设置最小生成树的顶点集合;
            minTree._vertexs = _vertexs;
            //设置最小生成树的顶点映射;
            minTree._vIndexMap = _vIndexMap;
            //设置最小生成树邻接矩阵的大小.
            minTree._matrix.resize(n, vector<W>(n, MAX_W));

            priority_queue<Edge, vector<Edge>, greater<Edge>> minHeap;

            //将所有边放到优先级队列中;
            for(int i = 0; i < n; i++)
            {
                //只用遍历一般矩阵, 因为无向图的对称.
                for(int j = 0; j < i; j++)
                {
                    if(_matrix[i][j] != MAX_W)
                    {
                        minHeap.push(Edge(i, j, _matrix[i][j]));
                    }
                }
            }

            n个顶点的并查集;
            UnionFindSet ufs(n);
            int count = 0;//选择边的个数;
            W totalWeight = W();//总权重;

            while(!minHeap.empty() && count < n-1)
            {
                //取出优先级队列的最小的边;
                Edge minEdge = minHeap.top();
                minHeap.pop();
                int srci = minEdge._srci;
                int desti = minEdge._desti;
                W weight = minEdge._weight;

                //两个边不属于一个集合.
                if(!ufs.InSameSet(srci, desti))
                {
                    minTree.addEdge(srci, desti, weight);
                    //合并两个顶点.
                    ufs.UnionSet(srci, desti);
                    count++;
                    totalWeight += weight;
                    cout << "选边: " << _vertexs[srci] << "->" << _vertexs[desti] << ":" << weight << endl;
                }
                else
                {
                    cout << "成环: " << _vertexs[srci] << "->" << _vertexs[desti] << ":" << weight << endl;
                }
            }
            if(count == n - 1)
            {
                cout << "构建最小生成树成功" << endl;
                return totalWeight;
            }
            else
            {
                cout << "无法构成最小生成树" << endl;
                return W();
            }
        }

        W Prim(Graph<V, W, MAX_W, Direction>& minTree, const V& start)
        {
            int n = _vertexs.size();

            //设置最小生成树的顶点集合;
            minTree._vertexs = _vertexs;
            //设置最小生成树的顶点映射;
            minTree._vIndexMap = _vIndexMap;
            //设置最小生成树邻接矩阵的大小.
            minTree._matrix.resize(n, vector<W>(n, MAX_W));

            int starti = getVertexIndex(start);
            vector<bool> forest(n, false);
            forest[starti] = true;
            priority_queue<Edge, vector<Edge>, greater<Edge>> minHeap;

            for(int i = 0; i < n; i++)
            {
                if(_matrix[starti][i] != MAX_W)
                {
                    minHeap.push(Edge(starti, i, _matrix[starti][i]));
                }
            }

            int count = 0;
            W totalWeight = W();
            while(!minHeap.empty() && count < n - 1)
            {
                Edge minEdge = minEdge.top();
                minHeap.pop();
                int srci = minEdge._srci, desti = minEdge._desti;
                W weight = W();

                if(forest[desti] == false)
                {
                    for(int i = 0; i < n; i++)
                    {
                        if(_matrix[desti][i] != MAX_W && forest[i] == false)
                        {
                            minHeap.push(Edge(desti, i, _matrix[desti][i]));
                        }
                    }
                    minTree._addEdge(srci, desti, weight);
                    forest[desti] = true;
                    totalWeight += weight;
                    cout << "选边: " << _vertexs[srci] << "->" << _vertexs[desti] << ":" << weight << endl;
                }
                else
                {
                    cout << "成环" << _vertexs[srci] << "->" << _vertexs[desti] << ":" << weight << endl;
                }
            }
            if(count == n - 1)
            {
                cout << "构建最小生成树成功" << endl;
                return totalWeight;
            }
            else
            {
                cout << "无法构建最小生成树" << endl;
                return W();
            }
        }

        void Dijkstra(const V& src, vector<W>& dist, vector<int>& parentPath)
        {
            int n = _vertexs.size();
            int srci = getVertexIndex(src);
            //各个顶点权重初始化;
            dist.resize(n, MAX_W);
            //顶点的前驱初始值.
            parentPath.resize(n, -1);

            dist[srci] = W();//源顶点权重设置;
            vector<bool> S(n, false);//使用过顶点数组;
            for(int i = 0; i < n; i++)
            {
                //最小权重;
                W minW = MAX_W;
                //最小权重的顶点;
                int u = -1;
                for(int j = 0; j < n; j++)
                {
                    //顶点没有使用过并且它的权重小于最小权重;
                    if(S[j] == false && dist[j] < minW)
                    {
                        //改变最小权重和最小权重的结点;
                        minW = dist[j];
                        u = j;
                    }
                }
                S[u] = true;

                //对连接出去的顶点进行松弛更新;
                for(int b = 0; v < n; v++)
                {
                    //如果u顶点到v顶点相连, 并且v顶点没有使用过, 其次就是最小权重数组dist的u顶点+权重u到v小于最小权重dist的v顶点;
                    //就改变dist的v顶点的最小权重, 并且建立一下上一个顶点.
                    if(S[v] == false && _matrix[u][v] != MAX_W && dist[u] + _matrix[u][v] < dist[v])
                    {
                        dist[v] = dist[u] + _matrix[u][v];
                        parentPath[v] = u;
                    }
                }
            }
        }

        void printShortPath(const V& src, const vector<W>& dist, const vector<int>& parentPath)
        {
            int n = _vertexs.size();
            int srci = getVertexIndex(src);

            for(int i = 0; i < n; i++)
            {
                vector<int> path;
                int cur = i;
                //cur从结点开始向前遍历找上一个顶点.
                while(cur != -1)
                {
                    path.push_back(cur);
                    cur = parentPath[cur];
                }
                revese(path.begin(), path.end());

                //打印顶点元素, 以及路径的权重.
                for(int j = 0; j < path.size(); j++)
                {
                    cout << _vertexs[path[j]] << "->";
                }
                cout << "路径的权重: " << dist[i] << " " <<endl;
            }
        }

        void BellmanFord(const V& src, vector<W>& dist, vector<int>& parentPath)
        {
            int n = _vertexs.size();
            int srci = getVertexIndex(src);
            dist.resize(n, MAX_W);
            parentPath.resize(n, -1);

            dist[srci] = W();
            for(int k = 0; k < n - 1; k++)
            {
                bool update = false;
                for(int i = 0; i < n; i++)
                {
                    for(int j = 0; j < n; j++)
                    {
                        if(_matrix[i][j] != MAX_W && dist[i] != MAX_W && dist[i] + _matrix[i][j] < dist[j])
                        {
                            dist[j] = dist[i] + _matrix[i][j];
                            parentPath[j] = i;
                            update = true;
                        }
                    }
                }
                if(update == false)
                {
                    break;
                }
            }

            //如果n-1轮还可以更新就是带有负权重.
            for(int i = 0; i < n; i++)
            {
                for(int j = 0; j < n; j++)
                {
                    if(_matrix[i][j] != MAX_W && dist[i] + _matrix[i][j] < dist[j])
                    {
                        //带负权重无法计算出最小路径.
                        return false;
                    }
                }
            }
            return true;
        }

        void FloydWarshall(vector<vector<W>>& vvDist, vector<vector<int>>& vvparentPath)
        {
            int n = _vertexs.size();
            vvDist.resize(n, vector<W>(n, MAX_W));
            vvparentPath.resize(n, vector<int>(n, -1));

            for(int i = 0; i < n; i++)
            {
                for(int j = 0; j < n; j++)
                {
                    if(_matrix[i][j] != MAX_W)
                    {
                        vvDist[i][j] = _matrix[i][j];
                        vvparentPath[i][j] = i;
                    }
                    if(i == j)
                    {
                        vvDist[i][j] = W();
                    }
                }
            }

            for(int k = 0; k < n; k++)
            {
                for(int i = 0; i < n; i++)
                {
                    for(int j = 0; j < n; j++)
                    {
                        if(vvDist[i][k] != MAX_W && vvDist[k][j] != MAX_W 
                        && vvDist[i][k] + vvDist[k][j] < vvDist[i][j])
                        {
                            vvDist[i][j]= vvDist[i][k] + vvDist[k][j];
                            vvparentPath[i][j] = vvparentPath[k][j];
                        }
                    }
                }
            }
        }

    private:
        vector<V> _vertexs;               // 顶点集合;
        unordered_map<V, int> _vIndexMap; // 顶点映射的下标;
        vector<vector<W>> _matrix;        //邻接矩阵的

    };

}


// int main()
// {
//     Matrix::Graph<char, int, INT_MAX> g("0123", 4);
//     g.addEdge('0', '1', 1);
//     g.addEdge('0', '3', 4);
//     g.addEdge('1', '3', 2);
//     g.addEdge('1', '2', 9);
//     g.addEdge('2', '3', 8);
//     g.addEdge('2', '1', 5);
//     g.addEdge('2', '0', 3);
//     g.addEdge('3', '2', 6);
//     g.print();
//     return 0;
// }

namespace LinkTable
{
    template<class W>
    struct Edge
    {
        //int _srci; //源顶点下标;t
        int _desti;//目标顶点下标.
        W _weight; //边权重;
        Edge<W>* _next; // 连接指针;

        Edge(int desti, const W& weight)
            :_desti(desti)
            ,_weight(weight)
            ,_next(nullptr)
        {}
    };


    template <class V, class W, W MAX_W = INT_MAX, bool Direction = false>
    class Graph
    {
        typedef Edge<W> Edge;

    public:
        Graph(const V* vertexs, int n)
            :_vertexs(vertexs, vertexs + n)
            ,_LinkTable(n, nullptr)
        {
            for(int i = 0; i < n; i++)
            {
                _vIndexMap[vertexs[i]] = i;
            }
        }


        int getVertexIndex(const V &v)
        {
            auto iter = _vIndexMap.find(v);
            if (iter != _vIndexMap.end())
            {
                return iter->second;
            }
            else
            {
                throw invalid_argument("不存在的结点");
                return -1;
            }
        }

        int addEdge(const V& src, const V& dest, const W& weight)
        {
            int srci = getVertexIndex(src);
            int desti = getVertexIndex(dest);

            Edge* sdEdge = new Edge(desti, weight);
            sdEdge->_next = _LinkTable[srci];
            _LinkTable[srci] = sdEdge;

            if(Direction == false)
            {
                Edge* dsEdge = new Edge(srci, weight);
                dsEdge->_next = _LinkTable[desti];
                _LinkTable[desti] = dsEdge;
            }
        }


        void print()
        {
            int n = _vertexs.size();

            for(int i = 0; i < n; i++)
            {
                cout << "[" << i << "]->" << _vertexs[i];
            }
            cout << endl << endl;

            for(int i = 0; i < n; i++)
            {
                Edge* cur = _LinkTable[i];
                cout << "[" << i << ":" << _vertexs[i] << "]->";

                while(cur)
                {
                    cout << "[" << cur->_desti << ":" << _vertexs[cur->_desti] << ":" << cur->_weight << "]->";
                    cur = cur->next;
                }
                cout << nullptr;
            }
        }

    private:
        vector<V> _vertexs;
        unordered_map<V, int> _vIndexMap;
        vector<Edge*> _LinkTable;
    };
} 